1. Field of the Invention
This invention describes a sequential coding system which converts unconstrained data into a constrained format in an invertible manner. The described invention is particularly useful in dynamic memory systems.
2. Description of the Prior Art
Various ways have been proposed in the past for increasing the recorded data density on mediums such as magnetic discs or tapes and in other similar media. One approach utilized is known as run-length-limited coding which requires that each "1" in a coded bit sequence must be separated from the nearest adjacent "1" by a specified number of "0's". This number must be at least equal to a minimum quantity d because of intersymbol interference but must not exceed a maximum of k which is required for self-clocking purposes. Codes following this format are generally referred to as (d,k) run-length-limited codes. The present invention relates to a particular code suited for magnetic recording channels wherein d=1 and k=7. To convert unconstrained data into a (d,k)-constrained format generally requires that m unconstrained bits be mapped into n constrained bits, where m&lt;n. The ratio m/n is usually referred to as the coding rate or efficiency. It is obviously desirable to maximize this rate. The tradeoffs usually considered in maximizing the rate are the decoding look-ahead and the hardware complexity.
Raising the coding efficiency or rate at the expense of decoding look-ahead generally results in increasing the error propagation. That is, a single bit error introduced in the code stream will cause a certain number of subsequent bits to also be erroneous before the coding algorithm becomes self-correcting. It is always desirable to minimize error propagation. It has been found that a coding rate of 2/3 is optimal for the (1,7) code.
U.S. Pat. No. 3,689,899 to P. A. Franaszek discloses two possible (d,k) codes (1,8) and (2,7). The potential data codes are variable length, fixed rate state independent block codes. The coding rate of the (1,8) code is 2/3 and its code dictionary consists of 16 code words whose lengths vary from 3 to 9 bits, in multiples of 3. The (2,7) code has a coding rate of 1/2 and its dictionary consists of seven words with lengths varying from 2 bits to 8 bits, in multiples of 2.
The following two references both disclose (d,k) codes having the particular run-length parameters (1,7) and a coding rate of 2/3 which are the same parameters chosen and implemented in the herein disclosed coding method. These two references are the article "Efficient Code for Digital Magnetic Recording" by P. A. Franaszek, in the IBM Technical Disclosure Bulletin, Vol. 23, No. 9, February 1981, page 4375, which is a bounded delay code, and the article "An Optimization of Modulation Codes in Digital Recording" by T. Horiguchi and K. Morita, IEEE Transactions on Magnetics, Vol. MEG-12, No. 6, November 1976, page 740. While the coding methods described in both of these articles will produce codes having the same (d,k) values as the herein disclosed code and the same coding rate 2/3, the actual coding tables will be different and the coding method differs in a number of respects.
The (1,7) code constructed by Franaszek has a finite look-ahead encoder and a variable length decoder. The encoder converts two data bits into 3 constrained bits by employing look-ahead of two additional data bits. The coded output is thus a function of the present two and the future two data bits. The decoder maps 3 constrained bits into two data bits as a function of the present channel state and for a particular channel state this dependence extends to the previous channel state. The error propagation of this code is 6 bits. The codes constructed by Horiguchi et al are variable length fixed rate codes. The error propagation of their code is 6 bits.